Rotate Array (LeetCode 189)

thoughts

• 將陣列右旋轉 k 步。
• 常見解法：
  • 使用額外陣列 (O(n) 空間)
  • 反轉法 (O(1) 空間)：
  • 反轉整個陣列
  • 反轉前 k 部分
  • 反轉後 n-k 部分

kotlin

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val step = k % n
        reverse(nums, 0, n - 1)
        reverse(nums, 0, step - 1)
        reverse(nums, step, n - 1)
    }

    private fun reverse(nums: IntArray, l: Int, r: Int) {
        var left = l
        var right = r
        while (left < right) {
            val tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp
            left++
            right--
        }
    }
}

follow up

• 如果 nums 非常大，不允許複製陣列，怎麼處理？（必須 O(1) 空間 in-place）
• 如果 nums 是 串流資料，只能單向讀取，怎麼旋轉？
• 如果 k 很大（例如 10^9），如何最佳化？